/*
 * @lc app=leetcode.cn id=1414 lang=typescript
 *
 * [1414] 和为 K 的最少斐波那契数字数目
 */

// @lc code=start
function findMinFibonacciNumbers(k: number): number {
  const fibonacci = [1];
  let a = 1;
  let b = 1;
  // 计算小于等于k的斐波那契数列
  while (a + b <= k) {
    const c = a + b;
    fibonacci.push(c);
    a = b;
    b = c;
  }

  let ans = 0;
  for (let i = fibonacci.length - 1; i >= 0; i--) {
    const num = fibonacci[i];
    if (k >= num) {
      k -= num;
      ans++;
    }
  }

  return ans;
}
// @lc code=end
